package 力扣日常刷题.木22二月.第14天220;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 帅小伙
 * @date 2022/2/20
 * @description
 * 找比两侧当前位置高的最大值
 */
public class Demo113单调栈接雨水 {

    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        // 保存 比
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && height[i] > height[d.peek()]) {
                int cur = d.pop();
                // 如果栈内没有元素  说明当前位置左边没有高的柱子  跳过
                if(d.isEmpty()) continue;

                int l  = d.peek(),r = i;
                int w = r - l + 1 - 2;
                int h = Math.min(height[l],height[r]) - height[cur];
                ans += w * h;
            }
            d.push(i);
        }
        return ans;
    }

}
